// 有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。
// 给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。
// 为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，
// 接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，
// 重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。
// 最后返回经过上色渲染后的图像。

// 暴露接口
function floodFill(image: number[][], sr: number, sc: number, newColor: number): number[][] {
    // 安全检测
    if (image.length < 1) {
        return image;
    }
    const directions: number[][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];// 方向向量
    flood_DFS(image, sr, sc, newColor, directions);// 开始深度优先遍历
    return image;
};
// 深度优先遍历方法
function flood_DFS(image: number[][], sr: number, sc: number, newColor: number, directions: number[][]) {
    if (image[sr][sc] === newColor) {// 如果当前元素已经上色过，直接返回
        return;
    }
    const rows: number = image.length;// 计算行列
    const cols: number = image[0].length;
    let curr: number = image[sr][sc];// 当前元素值
    for (let dire of directions) {
        let newX: number = sr + dire[0];
        let newY: number = sc + dire[1];
        if (newX >= 0 && newY >= 0 && newX < rows && newY < cols && curr === image[newX][newY]) {// 判断方法
            flood_DFS(image, newX, newY, newColor, directions);
        }
        image[sr][sc] = newColor;// 上色
    }
}

// 这道题目是比较明显的深度优先遍历搜索的算法
// 我们从给定的起点开始，进行深度优先搜索。
// 每次搜索到一个方格时，如果该方格的颜色已经更新过，那就直接返回以防止重复搜索；
// 如果不相同，则继续进行后续操作。
// 注意：因为初始位置的颜色会被修改，所以我们需要在搜索的终点到达后再统一上色
// 总体来说是难点在于考察递归的出口在何处。
